#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
//可以去学一些主流的方法
//最大的size=capacity-1

typedef struct 
{
    int *nums;
    int capacity;
    int front, rear;    
}Deque;
/*构造函数*/
Deque *newDeque(int capacity)
{
    Deque *q = (Deque *)malloc(sizeof(Deque));
    q->capacity = capacity;
    q->nums = (int *)malloc(capacity * sizeof(int));
    q->front = 0;
    q->rear =  0; //指向队尾下一个空的地方 
}
/*析构*/
void delDeque(Deque *q)
{
    free(q->nums);
    free(q);
}
/*获取有几个人在排队*/
int size(Deque *q)
{
    return (q->rear - q->front + q->capacity)%q->capacity;
}
/*获取容量*/
// int capacity(Deque *q)
// {
//     return q->capacity;
// }

/*索引位置*/
int get_idx(Deque *q, int i)
{
    return (i+q->capacity) % q->capacity;
}
/*将元素添加至队首*/
void push_first(Deque *q, int value)
{
    if (size(q)+1 == q->capacity)
    {
        printf("双向队列已满\n");
        return;
    }
    q->front = get_idx(q,q->front-1);
    q->nums[q->front] = value;
}
/*将元素添加至队尾*/
void push_last(Deque *q, int value)
{
    if (size(q)+1 == q->capacity)
    {
        printf("双向队列已满\n");
        return;
    }
    q->nums[q->rear] = value;
    q->rear = get_idx(q,q->rear+1);
}
/*访问队首元素 */
int peek_first(Deque *q)
{
    if (size(q) == 0)
    {
        printf("双向队列为空\n");
        return INT_MAX;
    }
    return q->nums[q->front];
}
/*访问队尾元素*/
int peek_last(Deque *q)
{
    if (size(q) == 0)
    {
        printf("双向队列为空\n");
        return INT_MAX;
    }
    return q->nums[get_idx(q,q->rear-1)];
}
/*删除队首元素*/
int pop_first(Deque *q)
{
    int value = peek_first(q);
    q->front = get_idx(q, q->front+1);
    return value;
}
/*删除队尾元素*/
int pop_last(Deque *q)
{
    int value = peek_last(q);
    q->rear = get_idx(q, q->rear-1);
    return value;
}
/*打印双向队列*/
void printDeque(Deque *q)
{
    if (size(q) == 0)
    {
        printf("双向队列为空\n");
        return;
    }
    for (int i = q->front; i < q->front+size(q); i++)
    {
        printf("%d ", q->nums[get_idx(q,i)]);
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    // 初始化1 3 2 5 4 99
    Deque *q = newDeque(7);
    push_last(q, 1);
    push_last(q, 3);
    push_last(q, 2);
    push_last(q, 5);
    push_last(q, 4);
    push_last(q, 99);
    printDeque(q);
    // 队首，队尾
    printf("上面的队首:%d,队尾:%d\n", peek_first(q), peek_last(q));
    printf("上面的front:%d,rear:%d\n", q->front, q->rear);

    // 队首出队
    int val;
    val = pop_first(q);
    printf("队首出队:");
    printDeque(q);
    printf("上面的front:%d,rear:%d\n", q->front, q->rear);
    // 队尾出队
    val = pop_last(q);
    printf("队尾出队:");
    printDeque(q);
    printf("上面的front:%d,rear:%d\n", q->front, q->rear);
    // 队尾入队
    push_last(q, 999);
    printf("队尾入队:");
    printDeque(q);
    printf("上面的front:%d,rear:%d\n", q->front, q->rear);

    // front,rear极限测试
    // 队尾出队，队首入队
    pop_last(q);
    push_first(q,11);
    pop_last(q);
    push_first(q,12);
    pop_last(q);
    push_first(q,13);
    printDeque(q);
    printf("上面的front:%d,rear:%d\n", q->front, q->rear);

    // 析构
    delDeque(q);
    return 0;
}
